import java.util.ArrayList;

public class LinkedListMap <K,V> implements Map<K,V>{
    private Node dummyHead;
    private int size;

    public LinkedListMap() {
        dummyHead = new Node();
        size = 0;
    }

    /**
     * 根据键值获取链表中的节点。
     *
     * @param key 要查找的键值。
     * @return 如果找到匹配的节点，则返回该节点；否则返回null。
     */
    private Node getNode(K key){
        // 从虚拟头节点的下一个节点开始遍历，虚拟头节点用于简化链表操作
        Node cur = dummyHead.next;

        // 遍历链表直到当前节点为空
        while (cur != null){
//            if (cur.key != null) {
                // 如果当前节点的键值与目标键值相等，则返回当前节点
                if (cur.key.equals(key)) {
                    return cur;
                }
//            }
            // 如果当前节点的键值与目标键值不相等，则移动到下一个节点
            cur = cur.next;
        }
        // 如果遍历完整个链表都没有找到匹配的节点，则返回null
        return null;
    }

    /**
     * 向链表映射表中添加一个新的键值对。
     * 如果键已经存在，则更新该键对应的值；否则，创建一个新的节点并添加到链表中。
     *
     * @param key 要添加或更新的键。
     * @param value 要添加或更新的值。
     */
    @Override
    public void add(K key, V value) {
        // 尝试获取与给定键对应的节点。
        Node node = getNode(key);

        // 如果节点不存在，则创建一个新节点并将其添加到链表的头部。
        if (node == null){
            dummyHead.next = new Node(key,value,dummyHead.next);
            size ++;
        } else {
            // 如果节点存在，则更新该节点的值。
            node.value = value;
        }
    }

    /**
     * 和单链表删除节点逻辑相同
     * @param key 想要删除的key值
     * @return
     */
    @Override
    public V remove(K key) {
        // 从虚拟头节点开始遍历
        Node prev = dummyHead;
        while (prev.next != null) {
            // 如果当前节点的元素等于要删除的元素，则停止遍历
            if (prev.next.key.equals(key)) {
                break;
            }
            // 否则，移动到下一个节点
            prev = prev.next;
        }

        // 这里又一次判断prev.next是为了如果找完整个链表后没有找到要删除的元素（即想要删除的元素不存在）不执行删除节点操作
        if (prev.next != null) {
            // 删除节点并更新链表
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size --;
            return delNode.value;
        }
        return null;
    }

    /**
     * 检查集合中是否包含指定的键。
     *
     * @param key 要检查的键。
     * @return 如果集合中存在该键，则返回true；否则返回false。
     */
    @Override
    public boolean contains(K key) {

        // 通过getNode方法查找指定键对应的节点，如果找到则返回该节点，否则返回null。
        // 因此，如果getNode返回非null，说明集合中包含该键。
        return getNode(key) != null;
    }


    @Override
    public V get(K key) {
        Node node = getNode(key);

        return node == null?null:node.value;
    }

    /**
     * Updates the value associated with a specific key.
     * Throws an IllegalArgumentException if the key does not exist in the map.
     *
     * @param key The key whose value is to be updated.
     * @param newValue The new value to be associated with the key.
     * @throws IllegalArgumentException if the key does not exist.
     */
    @Override
    public void set(K key, V newValue) {
        /* Attempt to get the node corresponding to the key */
        Node node = getNode(key);
        /* If the node does not exist, throw an exception */
        if (node == null){
            throw new IllegalArgumentException(key + "doesn't exist!");
        }
        /* Update the value of the node */
        node.value = newValue;
    }


    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private class Node {

        public K key;
        public V value;
        public Node next;

        public Node(K key,V value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public Node(K key) {
            this(key,null, null);
        }

        public Node() {
            this(null,null, null);
        }

        @Override
        public String toString() {
            return key.toString()+" : "+value.toString();
        }
    }

    public static void main(String[] args) {
        System.out.println("Pride and Prejudice");

        ArrayList<String> words = new ArrayList<>();

        if (FileOperation.readFile("/Users/liuyifan/IdeaProjects/Data-Structures/07-Map/src/pride-and-prejudice.txt",words)){
            System.out.println("Total words: "+words.size());

            LinkedListMap<String, Integer> map = new LinkedListMap<>();

            for (String word:words){
                if (map.contains(word)){
                    map.set(word, map.get(word)+1);
                }else {
                    map.add(word,1);
                }
            }
            System.out.println("Total different words: "+map.getSize());
            System.out.println("Frequency of PRIDE: "+map.get("pride"));
            System.out.println("Frequency of PREJUDICE: "+map.get("prejudice"));
        }
    }
}
